package com.zlk.algorithm.huawei.leetcode.dp;

/**
 * @program: algorithm
 * @ClassName Code51_canPartition
 * @description:
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * 示例 1：
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 * 示例 2：
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集。
 * @author: slfang
 * @create: 2025-01-16 09:59
 * @Version 1.0
 **/
public class Code51_canPartition {

    public boolean canPartition1(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }



    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum =0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        int m = sum/2;
        //dp 就是从nums中选取数和组成half
        //本质还是0,1 背包问题
        //dp[i][j] 0-i范围上 选取的对象和等于j 是否为true
        //    不要i dp[i-1][j]
        //    要i   dp[i-1][j-nums[i]]
        //   ||
        //
        boolean[][] dp = new boolean[n+1][m+1];
        //一个不选，和为0 为true
        dp[0][0]=true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <=m; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1]){
                    dp[i][j] = dp[i][j]||dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][m];
    }





}
